package org.example.top40;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class main28 {
    //合并区间
    //输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
    //输出：[[1,6],[8,10],[15,18]]
    //思路：根据p[0]-q[0]排序
    //L，R 和res的最后一个数组的[1]比较，合并不满足正常加入，满足max(R,已经加入到res中的R比较)
    public static void main(String[] args) {
        int[][] arr = {
                {1, 3},
                {2, 6},
                {8, 10},
                {15, 18}
        };
        int[][] res = merege(arr);
        for (int[] row : res) {
            System.out.print("[");
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println("]");
        }
    }

    private static int[][] merege(int[][] arr) {
        Arrays.sort(arr, (p, q) -> p[0] - q[0]);
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int L=arr[i][0];
            int R=arr[i][1];
            if(res.size()==0||res.get(res.size()-1)[1]<L){
                res.add(new int[]{L,R});
            }else {
                res.get(res.size()-1)[1]=Math.max(R,res.get(res.size()-1)[1]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
